{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #First Missing Positive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: firstMissingPositive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #缺失的第一个正数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个未排序的整数数组 <code>nums</code> ，请你找出其中没有出现的最小的正整数。</p>\n",
    "请你实现时间复杂度为 <code>O(n)</code> 并且只使用常数级别额外空间的解决方案。\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,0]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,4,-1,1]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [7,8,9,11,12]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [first-missing-positive](https://leetcode.cn/problems/first-missing-positive/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [first-missing-positive](https://leetcode.cn/problems/first-missing-positive/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,0]', '[3,4,-1,1]', '[7,8,9,11,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        buckets = [0] * (n + 1)\n",
    "        for x in nums:\n",
    "            if x > 0 and x <= n:\n",
    "                buckets[x] += 1\n",
    "        for i in range(1, n+1):\n",
    "            if buckets[i] == 0:\n",
    "                return i\n",
    "        return n + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            cur = nums[i]\n",
    "            while cur and cur >= 1 and cur <= l:\n",
    "                tmp = nums[cur - 1]\n",
    "                nums[cur - 1] = None\n",
    "                cur = tmp\n",
    "        \n",
    "        i = 0\n",
    "        while i < l:\n",
    "            if nums[i] is None:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return i + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        #第一个循环去遍历Nums里的每一个元素\n",
    "        for i in range(len(nums)):\n",
    "            #如果当前这个数字在我们能够进行转移的范围内\n",
    "            if 0 < nums[i] and nums[i]< len(nums):\n",
    "                # if nums[i] != nums[nums[i]-1]:\n",
    "                #如果当前这个位置上的数字与它的index对应不上的话，我们会把它放到他应该在的正确的位置上去\n",
    "                #同时为了保证数组元素信息不丢失，那个正确位置上的信息我们也要拿过来。\n",
    "                while nums[i] != i + 1:\n",
    "                    nums[nums[i]-1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "                    #一旦换完后当前位置i上的元素出现以下任意一种情况都说明我们不用再换了\n",
    "                    if nums[i] <= 0 or nums[i] >= len(nums) or nums[i]==nums[nums[i]-1]:\n",
    "                        break\n",
    "        #上一段代码在干的事情就是我们让大于0小于len(nums)的元素全部到对应的位置上去\n",
    "        #比如nums为[1,3,-1,5,2],那么经过上面之后就变成[1,2,3,-1,5],能够对应上的数字全部已经正确排序，缺陷的(-1)的index+1就是缺失的第一个正数。\n",
    "        if len(nums)==0:return 1\n",
    "        #再次遍历数组\n",
    "        #jet是一个标识符，用来标志我们找没找到不符合的项\n",
    "        for i in range(len(nums)):\n",
    "            #找到的第一个大小与index不符的项，我们的答案就已经产生，就是当前index+1\n",
    "            if nums[i] != i + 1:\n",
    "                return i+1\n",
    "        #如果数组是[1,2,3]这种，每一项都符合，则缺失的是4,也就是len(nums) + 1\n",
    "        return nums[-1]+1\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        #第一个循环去遍历Nums里的每一个元素\n",
    "        for i in range(len(nums)):\n",
    "            #如果当前这个数字在我们能够进行转移的范围内\n",
    "            if 0 < nums[i] and nums[i]< len(nums):\n",
    "                # if nums[i] != nums[nums[i]-1]:\n",
    "                #如果当前这个位置上的数字与它的index对应不上的话，我们会把它放到他应该在的正确的位置上去\n",
    "                #同时为了保证数组元素信息不丢失，那个正确位置上的信息我们也要拿过来。\n",
    "                while nums[i] != i + 1:\n",
    "                    nums[nums[i]-1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "                    #一旦换完后当前位置i上的元素出现以下任意一种情况都说明我们不用再换了\n",
    "                    if nums[i] <= 0 or nums[i] >= len(nums) or nums[i]==nums[nums[i]-1]:\n",
    "                        break\n",
    "     \n",
    "        #上一段代码在干的事情就是我们让大于0小于len(nums)的元素全部到对应的位置上去\n",
    "        #比如nums为[1,3,-1,5,2],那么经过上面之后就变成[1,2,3,-1,5],能够对应上的数字全部已经正确排序，缺陷的(-1)的index+1就是缺失的第一个正数。\n",
    "        \n",
    "        jet = 1\n",
    "        \n",
    "        #再次遍历数组\n",
    "        #jet是一个标识符，用来标志我们找没找到不符合的项\n",
    "        for i in range(len(nums)):\n",
    "            #找到的第一个大小与index不符的项，我们的答案就已经产生，就是当前index+1\n",
    "            if nums[i] != i + 1:\n",
    "                jet = 0\n",
    "                ans = i + 1\n",
    "                break\n",
    "        #如果数组是[1,2,3]这种，每一项都符合，则缺失的是4,也就是len(nums) + 1\n",
    "        if jet == 1:\n",
    "            ans = len(nums)+1\n",
    "        return ans\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 1\n",
    "        nums = sorted(nums)\n",
    "        count = 1\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] <= 0:\n",
    "                continue\n",
    "            if nums[i] == count:\n",
    "                if nums[i] != nums[i+1]:\n",
    "                    count += 1\n",
    "            else:\n",
    "                return count\n",
    "        if count == nums[len(nums) - 1]:\n",
    "            return count + 1\n",
    "        else:\n",
    "            return count\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nnums = [0]\n",
    "        for i in range(len(nums)):\n",
    "            nnums.append(nums[i])\n",
    "        nums = nnums\n",
    "        N = len(nums)\n",
    "        print(\"before\")\n",
    "        for i in range(len(nums)):\n",
    "            print(i,\" \",nums[i])\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] < 0 or nums[i]>=len(nums):\n",
    "                nums[i] = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[nums[i]%N] +=  N*(nums[i]%N)\n",
    "        print(\"after\")\n",
    "        for i in range(len(nums)):\n",
    "            print(i,\" \",nums[i])\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] < N:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if(len(nums) == 0):\n",
    "            return 1\n",
    "        \n",
    "        for i in range(0, len(nums)):\n",
    "            while(0 < nums[i] < len(nums) and nums[nums[i]-1] != nums[i]):\n",
    "                print(nums)\n",
    "                temp = nums[nums[i]-1]\n",
    "                nums[nums[i]-1] = nums[i]\n",
    "                nums[i] = temp\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            if(i != nums[i]-1):\n",
    "                return i+1\n",
    "        \n",
    "        return len(nums)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     #寻找没有出现的 最小的正整数\n",
    "#     def firstMissingPositive(self, nums: 'List[int]') -> 'int':\n",
    "#         for i in range(len(nums)):\n",
    "#             while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:\n",
    "#                 nums[i], nums[nums[i]-1] = nums[nums[i]-1],nums[i]\n",
    "#         for i in range(len(nums)):\n",
    "#             if i+1 != nums[i]:\n",
    "#                 return i+1\n",
    "#         return len(nums)+1\n",
    "class Solution(object):\n",
    "    def firstMissingPositive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)):\n",
    "            while nums[i]>0 and nums[i]<=len(nums) and nums[nums[i]-1]!=nums[i]:\n",
    "                nums[nums[i]-1],nums[i] = nums[i],nums[nums[i]-1]\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i]!=(i+1):\n",
    "                return i+1\n",
    "        return len(nums)+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\r\n",
    "        def _swap(nums,i,j):\r\n",
    "            nums[i],nums[j]=nums[j],nums[i]\r\n",
    "        size=len(nums)\r\n",
    "        for i in range(size):\r\n",
    "            while 1<=nums[i]<=size and nums[i]!=nums[nums[i]-1]:\r\n",
    "                _swap(nums,i,nums[i]-1)\r\n",
    "        for i in range(size):\r\n",
    "            if i+1!=nums[i]:\r\n",
    "                return i+1\r\n",
    "        return size+1\r\n",
    "\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] <= 0:\n",
    "                nums[i] = n + 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            num = abs(nums[i])\n",
    "            if num <= n:\n",
    "                nums[num - 1] = -abs(nums[num - 1])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                return i + 1\n",
    "        \n",
    "        return n + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        for i in range(1,2**31-1):\n",
    "            if i not in nums:\n",
    "                return i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num not in dic:\n",
    "                dic[num] = 1\n",
    "            else:\n",
    "                dic[num] += 1\n",
    "        i = 1\n",
    "        while True:\n",
    "            if i not in dic:\n",
    "                return i\n",
    "            i += 1\n",
    "        '''\n",
    "        size = len(nums)\n",
    "        for i in range(size):\n",
    "            # 先判断这个数字是不是索引，然后判断这个数字是不是放在了正确的地方\n",
    "            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:\n",
    "                self.__swap(nums, i, nums[i] - 1)\n",
    "\n",
    "        for i in range(size):\n",
    "            if i + 1 != nums[i]:\n",
    "                return i + 1\n",
    "\n",
    "        return size + 1\n",
    "\n",
    "    def __swap(self, nums, index1, index2):\n",
    "        nums[index1], nums[index2] = nums[index2], nums[index1] \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "                # nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]\n",
    "     \n",
    "        for i in range(n):\n",
    "            if i + 1 != nums[i]:\n",
    "                return i + 1\n",
    "        return n + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        i, n = 0, len(nums)\n",
    "\n",
    "        while i < n:\n",
    "            j = nums[i] - 1\n",
    "            if n > nums[i] > 0 and nums[i] != nums[j]:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx + 1 != num:\n",
    "                return idx + 1\n",
    "        return n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        lis = [i for i in range(1,302)]\n",
    "        nums=list(set(nums))\n",
    "        nums.sort()\n",
    "        if nums[-1]<=0:\n",
    "            return 1\n",
    "        for i in nums:\n",
    "            if i > 0:\n",
    "                w = nums.index(i)\n",
    "                j = i\n",
    "                break\n",
    "        if j > 1:\n",
    "            return 1\n",
    "        for i in range(w, len(nums)):\n",
    "            if i==len(nums)-1 and lis[i - w] == nums[i]:\n",
    "                return lis[i-w+1]\n",
    "            if lis[i - w] != nums[i]:\n",
    "                return lis[i-w]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        def qsort(array):\n",
    "            if len(array)<2:\n",
    "                return array\n",
    "            else:\n",
    "                pivot=array[0]\n",
    "                less=[i for i in array[1:] if i>0 and i<=pivot]\n",
    "                more=[i for i in array[1:] if i>0 and i>pivot]\n",
    "                return qsort(less)+[pivot]+qsort(more)\n",
    "        \n",
    "        nums=qsort(nums)\n",
    "        if nums and nums[0]<=0:\n",
    "            nums=nums[1:]\n",
    "\n",
    "        if len(nums)==0:\n",
    "            return 1\n",
    "        else:\n",
    "            ans=1\n",
    "            i=0\n",
    "            while i<len(nums) and nums[i]<=ans:\n",
    "                ans=nums[i]+1\n",
    "                i+=1\n",
    "            return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums=[i for i in nums if i>0]\n",
    "        for i in list(range(1,100000)):\n",
    "            if i not in nums:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        '''\n",
    "        :param nums: List[int]\n",
    "        :return: int\n",
    "        '''\n",
    "        def backtrack(nums, pos):\n",
    "            out = -1\n",
    "            if len(nums) == 0:\n",
    "                return pos\n",
    "            if nums[0] == pos:\n",
    "                out = backtrack(nums[1:], pos + 1)\n",
    "            elif nums[0] < pos:\n",
    "                nums[0], nums[len(nums)-1] = nums[len(nums)-1], nums[0]\n",
    "                out = backtrack(nums[:-1], pos)\n",
    "            elif nums[0] > pos:\n",
    "                if nums[0] > pos + len(nums) - 1:\n",
    "                    nums[0], nums[len(nums) - 1] = nums[len(nums) - 1], nums[0]\n",
    "                    out = backtrack(nums[:-1], pos)\n",
    "                elif nums[0] <= pos + len(nums) - 1:\n",
    "                    cc = pos + len(nums) - nums[0]\n",
    "                    if nums[cc] == nums[0]:\n",
    "                        out = backtrack(nums[1:], pos)\n",
    "                    else:\n",
    "                        nums[0], nums[cc] = nums[cc], nums[0]\n",
    "                        out = backtrack(nums, pos)\n",
    "\n",
    "            return out\n",
    "        see = backtrack(nums, 1)\n",
    "        return see"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                return i + 1\n",
    "        return n + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            while 0<nums[i]<len(nums) and nums[i]!=i+1 and nums[i]!=nums[nums[i]-1]:\n",
    "                n = nums[i]\n",
    "                nums[i],nums[n-1] = nums[n-1],nums[i]\n",
    "     \n",
    "        for i in range(len(nums)):\n",
    "            if i+1!=nums[i]:\n",
    "                return i+1 \n",
    "        return len(nums)+1\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        n = nums[i]\n",
    "        while i<len(nums):\n",
    "            # print(i,n,nums)\n",
    "            if not n or n<1 or n>len(nums) or  nums[n-1] is None:\n",
    "                i+=1\n",
    "                if i>=len(nums):\n",
    "                    break\n",
    "                n = nums[i]\n",
    "            # print(n)\n",
    "            else:\n",
    "                tmp = nums[n-1]\n",
    "                nums[n-1] = None\n",
    "                n = tmp\n",
    "            \n",
    "        # print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] is not None:\n",
    "                return i+1\n",
    "        else:\n",
    "            return len(nums)+1\n",
    "\n",
    "\n",
    "    def firstMissingPositive0(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        n = nums[i]\n",
    "        while i<len(nums):\n",
    "            # print(i,n,nums)\n",
    "            if not n or n<1 or n>len(nums) or  nums[n-1] is None:\n",
    "                i+=1\n",
    "                if i>=len(nums):\n",
    "                    break\n",
    "                n = nums[i]\n",
    "                continue\n",
    "            # print(n)\n",
    "            if nums[n-1]>0:\n",
    "                tmp = nums[n-1]\n",
    "                nums[n-1] = None\n",
    "                n = tmp\n",
    "            else:\n",
    "                nums[n-1]=None\n",
    "                i+=1\n",
    "                if i>=len(nums):\n",
    "                    break\n",
    "                n = nums[i]\n",
    "        # print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] is not None:\n",
    "                return i+1\n",
    "        else:\n",
    "            return len(nums)+1\n",
    "\n",
    "\n",
    "        \n",
    "    def firstMissingPositive1(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        m = max(nums)\n",
    "        for i in range(1,m):\n",
    "            if i not in nums:\n",
    "                return i \n",
    "        return max(1,m+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] <= 0 or nums[i] > n:\n",
    "                nums[i] = n+1\n",
    "\n",
    "        for i in range(n):\n",
    "            pvt = nums[i]\n",
    "            while (pvt > 0) and (pvt <= n):\n",
    "                next_pvt = nums[pvt-1]\n",
    "                nums[pvt-1] = 0\n",
    "                pvt = next_pvt\n",
    "        i = 0\n",
    "        while i < n and nums[i] == 0:\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return n+1\n",
    "        else:\n",
    "            return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        heapify(nums)\n",
    "        tmp = 0\n",
    "        while nums:\n",
    "            v = heappop(nums)\n",
    "            if v > 0:\n",
    "                if v > tmp + 1:\n",
    "                    return tmp + 1\n",
    "                else:\n",
    "                    tmp = v\n",
    "        return tmp + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 0\n",
    "        self.nums = None\n",
    "\n",
    "    def location(self, i):\n",
    "        \"\"\" 第 i 个元素开始归位 \"\"\"\n",
    "        carrot = self.nums[i] - 1\n",
    "        while True:\n",
    "            tmp = self.nums[carrot]\n",
    "            self.nums[carrot] = -1\n",
    "            if tmp < 1 or tmp > self.n: break\n",
    "            carrot = tmp - 1\n",
    "\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        self.nums = nums\n",
    "        self.n = len(nums)\n",
    "        for i in range(self.n):\n",
    "            if 0 < nums[i] <= self.n: continue\n",
    "            nums[i] = self.n + 1\n",
    "        for i in range(self.n):\n",
    "            if nums[i] < 1 or nums[i] > self.n: continue\n",
    "            self.location(i)\n",
    "        for i in range(self.n):\n",
    "            if nums[i] >= 0: return i + 1\n",
    "        return self.n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        heapify(nums)\n",
    "        max_int = 0\n",
    "        for i in range(len(nums)):\n",
    "            result = heappop(nums)\n",
    "            if result >= 1:\n",
    "                if (result - max_int) == 1:\n",
    "                    max_int = result\n",
    "                elif (result - max_int) > 1:\n",
    "                    return max_int + 1\n",
    "        return max_int + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] <= 0:\n",
    "                nums[i] = len(nums)+1\n",
    "        for j in range(len(nums)):\n",
    "            if nums[j] > len(nums) or nums[j] == -1:\n",
    "                continue\n",
    "            nums[nums[j]-1] = -1\n",
    "        for k in range(len(nums)):\n",
    "            if nums[k] != -1:\n",
    "                return k+1\n",
    "        return len(nums)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] <= 0:\n",
    "                nums[i] = len(nums)+1\n",
    "        for j in range(len(nums)):\n",
    "            if nums[j] > len(nums) or nums[j] == -1:\n",
    "                continue\n",
    "            nums[nums[j]-1] = -1\n",
    "        for k in range(len(nums)):\n",
    "            if nums[k] != -1:\n",
    "                return k+1\n",
    "        return len(nums)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        seen_n = 0\n",
    "        i = 0\n",
    "        seen_n = n in nums\n",
    "        while i < n:\n",
    "            if nums[i] is not None:\n",
    "                v = nums[i]\n",
    "                while 0 <= v < n and not (nums[v] is None):\n",
    "                    numsv = nums[v]\n",
    "                    nums[v] = None \n",
    "                    v = numsv\n",
    "            i += 1\n",
    "        print(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] is not None:\n",
    "                return i\n",
    "            if nums[i] == n:\n",
    "                seen_n = 1\n",
    "        return n + seen_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if (nums[i] <= 0 or nums[i] > n):\n",
    "                nums[i] = n + 1\n",
    "        for i in range(n):\n",
    "            if (abs(nums[i]) <= n):\n",
    "                nums[abs(nums[i]) - 1] = nums[i] if nums[abs(nums[i]) - 1] > n else -abs(nums[abs(nums[i]) - 1])\n",
    "                if (nums[i] > 0):\n",
    "                    nums[i] = n + 1\n",
    "        for i in range(n):\n",
    "            if (nums[i] > n):\n",
    "                return i + 1\n",
    "        return n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        for a in nums: #遍历每个座位，记当前坐着a号乘客\n",
    "            while 0<a<=len(nums) and a!=nums[a-1]:  #乘客a是正票但坐错了! 其座位被 ta=nums[a-1]占了\n",
    "                nums[a-1], a = a, nums[a - 1]  # a和ta两人互换则a对号入座。此后ta相当于新的a，去找自己的座位（循环执行）\n",
    "        for i in range(len(nums)):\n",
    "            if i+1!=nums[i]:return i+1  #找到首个没有对号入座的nums[i]!=i+1\n",
    "        return len(nums)+1  #满座，返回N+1\n",
    "\n",
    "\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 1:\n",
    "                nums[i] = N + 1\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] += 5\n",
    "\n",
    "        print(nums)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            n = nums[i]\n",
    "            if n > N + 5:\n",
    "                nums[i] = 0\n",
    "            if n < 0:\n",
    "                n *= -1\n",
    "                nums[i] = 1\n",
    "            if n >= 6 and n <= N + 5: # in range (1, N)\n",
    "                n -= 5\n",
    "                if nums[n - 1] == 0:\n",
    "                    nums[n - 1] = 1\n",
    "                elif nums[n - 1] > 5:\n",
    "                    nums[n - 1] *= -1\n",
    "            # print(nums)\n",
    "\n",
    "        # print(nums)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0 or nums[i] > 1:\n",
    "                return i + 1\n",
    "        return N + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums):\n",
    "        n = len(nums)\n",
    "\n",
    "        # 将数组中的每个数字放到正确的位置上\n",
    "        for i in range(n):\n",
    "            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "\n",
    "        # 找到第一个不在正确位置上的数字，即为缺失的最小正整数\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                return i + 1\n",
    "\n",
    "        # 如果数组中的所有数字都在正确位置上，缺失的是数组长度 + 1\n",
    "        return n + 1\n",
    "\n",
    "# 示例\n",
    "solution = Solution()\n",
    "nums = [1, 2, 0]\n",
    "result = solution.firstMissingPositive(nums)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        #原地哈希\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            while nums[i] >= 1 and nums[i] <= l and nums[i] != nums[nums[i]-1]:\n",
    "                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "        for i in range(l):\n",
    "            if nums[i] != i + 1:\n",
    "                return i + 1\n",
    "        return l + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums[:] = sorted(nums)\n",
    "        left = 0\n",
    "\n",
    "        while left < len(nums) and nums[left] < 1:\n",
    "            left += 1\n",
    "\n",
    "        \n",
    "        if left >= len(nums) or nums[left] > 1:\n",
    "            return 1\n",
    "\n",
    "        while left < len(nums):\n",
    "            if left == len(nums)-1:\n",
    "                return nums[left] + 1\n",
    "\n",
    "\n",
    "            if nums[left] + 1 == nums[left+1] or nums[left] == nums[left+1]:\n",
    "                left += 1\n",
    "            else:\n",
    "                return nums[left] + 1\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        l=[0]*len(nums)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            l[i-1]=i\n",
    "        ll=len(nums)\n",
    "        for i in nums:\n",
    "            if i<=0:\n",
    "                continue\n",
    "            elif i<=ll:\n",
    "                l[i-1]=ll+1\n",
    "        return min(l)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        # smallest missing: what does it look for \n",
    "        # uses O(1) space: nearly nothing saved\n",
    "        # how do we keep track of the number that is missing\n",
    "        l = len(nums)\n",
    "        M = 1 << 31\n",
    "\n",
    "        nums = [max(0, i) for i in nums]\n",
    "        for i, num in enumerate(nums):\n",
    "            num %= M\n",
    "            if num > 0 and num <= l:\n",
    "                nums[num - 1] += M\n",
    "\n",
    "        res = l + 1\n",
    "        for i, n in enumerate(nums, 1):\n",
    "            if n < M:\n",
    "                return i\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        def DSF(i):\n",
    "            if nums[i]==i+1:\n",
    "                return\n",
    "            if 0<nums[i]<len(nums)+1:\n",
    "                if nums[i]==nums[nums[i]-1]:\n",
    "                    return\n",
    "                nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]\n",
    "                DSF(i)\n",
    "        for i in range(len(nums)):\n",
    "            DSF(i)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]!=i+1:\n",
    "                return i+1\n",
    "        return len(nums)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        array = [0 for i in range(500000)];\n",
    "        array[0] = 1;\n",
    "        for i in nums:\n",
    "            if 0<i<500000:\n",
    "                array[i] = 1\n",
    "        return array.index(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            num = int(nums[i])\n",
    "            if 0 < num <= len(nums):\n",
    "                nums[num - 1] = str(nums[num - 1])\n",
    "        for i in range(len(nums)):\n",
    "            if type(nums[i]) == int:\n",
    "                return i + 1\n",
    "        return i + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        for i,v in enumerate(nums):\n",
    "            if isinstance(v, int):\n",
    "                if v <= len(nums) and v > 0:\n",
    "                    nums[v-1] = '{},o'.format(nums[v-1]) \n",
    "            if isinstance(v, str):\n",
    "                print(v)\n",
    "                index = int(v.split(',')[0])\n",
    "                if index > 0 and index <= len(nums):\n",
    "                    nums[index-1] = '{},o'.format(nums[index-1])\n",
    "        for i,v in enumerate(nums):\n",
    "            if isinstance(v, int):\n",
    "                return i + 1\n",
    "        return len(nums) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        minNums = [0 for i in range(int(5e5 + 9))]\n",
    "        for num in nums:\n",
    "            if num > 0 and num < 5e5 + 1:\n",
    "                minNums[num] = 1\n",
    "        for i in range(1,int(5e5 + 1)):\n",
    "            if minNums[i] != 1:\n",
    "                return i\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        v = [0] * 500005\n",
    "        for num in nums:\n",
    "            if 0 < num < 500004:\n",
    "                v[num] += 1\n",
    "        for i in range(1,500004):\n",
    "            if v[i] == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if i not in nums_set:\n",
    "                return i\n",
    "        return len(nums)+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        m=max(nums)\n",
    "        if m<=0:\n",
    "            return 1\n",
    "        nums=set(nums)\n",
    "        for i in range(1,m+2):\n",
    "            if i in nums:\n",
    "                continue\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        tar_set=set()\n",
    "        ans=1\n",
    "        for item in nums:\n",
    "            if(item == ans): ans+=1\n",
    "            while(ans in tar_set):\n",
    "                tar_set.remove(ans)\n",
    "                ans+=1\n",
    "            tar_set.add(item)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        def judge(nums_, l, r):\n",
    "            if l + 1 < nums_[l]: return l + 1\n",
    "            if nums_[r] == r - l + 1 or l == r: return r + 2\n",
    "            m = (l + r) >> 1\n",
    "            return v if (v := judge(nums_, l, m)) < nums_[m + 1] else judge(nums_, m + 1, r)\n",
    "        nums = sorted(set([x for x in nums if x > 0]))\n",
    "        return judge(nums, 0, len(nums) - 1) if nums else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        data = [0] * n\n",
    "        index = 0\n",
    "        for num in nums:\n",
    "            if num > 0: #获取正数\n",
    "                data[index] = num\n",
    "                index += 1\n",
    "        data = data[:index]\n",
    "        data = list(set(data))  #去重\n",
    "        data = sorted(data) #对正数排序\n",
    "        if len(data) == 0:\n",
    "            return 1\n",
    "        for index,num in enumerate(data):\n",
    "            if num - 1 != index:\n",
    "                return index + 1\n",
    "        return data[-1] + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        visited = set(list(range(1,len(nums)+2)))\n",
    "        for n in nums:\n",
    "            if n<=0: continue\n",
    "            if n not in visited:\n",
    "                return min(visited)\n",
    "            visited.remove(n)\n",
    "        return min(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 首先要明确我们的答案在区间 [1, len(nums) + 1] 之间，理由如下：\n",
    "# 如果数组全部元素都小于 1，那么最小未出现整数就是 1（下限）\n",
    "# 如果数组元素从 1 到 len(nums) 逐个递增，那么最小未出现整数就是 len(nums) + 1（上限）\n",
    "# 所以只需要记录数组在 [1, len(nums)] 范围内元素出现情况，如果都没出现，则返回 1；如果都出现了，则返回 len(nums) + 1\n",
    "# 如何记录？将元素有效范围，映射到数组索引 [0, len(nums) - 1] 上即可记录出现情况\n",
    "# 具体记录方式就是将数组修改为二维，第二维用 bool 类型判断是否出现\n",
    "# 最终结果就是找到数组中第一个有 False 的元素，返回其索引 + 1；若都没有 False，返回 len(nums) + 1\n",
    "\n",
    "# 将这个范围映射到索引范围上 [0, len(nums) - 1]，所以只需要找数组中在 [1, len(nums)] 范围的元素即可\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        # 首先遍历一遍数组修改数组结构\n",
    "        for ind in range(len(nums)):\n",
    "            nums[ind] = [nums[ind], False]\n",
    "\n",
    "        for ind in range(len(nums)):\n",
    "            if 1 <= nums[ind][0] <= len(nums):\n",
    "                nums[nums[ind][0] - 1][1] = True\n",
    "\n",
    "        # 访问最终 nums 数组找到第二维度非 True 的元素，结果为该元素下标 + 1\n",
    "        for ind in range(len(nums)):\n",
    "            if nums[ind][1] is False:\n",
    "                return ind + 1\n",
    "\n",
    "        return len(nums) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        mapping = dict()\n",
    "        for num in nums:\n",
    "            mapping[num] = 1\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            if i not in mapping:\n",
    "                return i\n",
    "        return len(nums) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from re import L\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        mapt = {}\n",
    "        for i in nums:\n",
    "            mapt[i] = mapt.get(i,0)+1\n",
    "        j = 1\n",
    "        while True:\n",
    "            if j not in mapt:\n",
    "                return j\n",
    "            j+=1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            dic[num] = num + 1\n",
    "        ans = 1\n",
    "        while ans in dic:\n",
    "            ans = dic[ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        n = len(nums)\n",
    "        res = {i+1 for i in range(n+1)}\n",
    "        for num in nums:\n",
    "            if num in res:\n",
    "                res.remove(num)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstMissingPositive(self, nums: List[int]) -> int:\n",
    "        pure=set(nums)                              #pure是nums中存在的值的集合\n",
    "        total=set()\n",
    "        for i in range(1,len(pure)+1):              #total是{1,2,3...,n}的集合\n",
    "            total.add(i)\n",
    "        if total-pure==set():                       #判断total-pure的差集。如果是空集，则total和pure完全一样，最小正整数是n+1\n",
    "            ans=len(pure)+1\n",
    "            return ans\n",
    "        else:                                       #如果不是空集，最小正整数是差集中最小的数\n",
    "            ans=min(total-pure)\n",
    "            return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
